{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How to solve the [water pouring puzzle](https://en.wikipedia.org/wiki/Water_pouring_puzzle#Variant_with_taps_and_sinks) programmatically.\n",
    "\n",
    "Given two jugs of capcity of 3 and 5 liters, acquire exactly 4 liters in a jug.  Assume an unlimited water supply, and that jugs can only be filled or emptied, i.e., no estimations.\n",
    "\n",
    "First to model the data: a mapping of jug sizes to their current quantity.  There are 3 primitive operations:\n",
    "* filling a jug to capacity\n",
    "* emptying a jug entirely\n",
    "* pouring from a source jug to a destination jug, until either the source is emptied or the destination is full"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Jugs(dict):\n",
    "    def fill(self, size):\n",
    "        self[size] = size\n",
    "\n",
    "    def empty(self, size):\n",
    "        self[size] = 0\n",
    "    \n",
    "    def pour(self, src, dest):\n",
    "        total = self[src] + self[dest]\n",
    "        self[src] = max(total - dest, 0)\n",
    "        self[dest] = min(total, dest)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's sufficient to solve the puzzle through sheer brute force: scanning every possible combination breadth-first.  Note the below implementations don't terminate unless a solution is found."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "CPU times: user 138 ms, sys: 2.28 ms, total: 140 ms\nWall time: 144 ms\n"
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[(0, 5), (3, 2), (0, 2), (2, 0), (2, 5), (3, 4)]"
     },
     "metadata": {},
     "execution_count": 2
    }
   ],
   "source": [
    "import itertools\n",
    "from functools import partial\n",
    "\n",
    "sizes = 3, 5\n",
    "operations = list(itertools.chain(\n",
    "    (partial(Jugs.fill, size=size) for size in sizes),\n",
    "    (partial(Jugs.empty, size=size) for size in sizes),\n",
    "    (partial(Jugs.pour, src=src, dest=dest)\n",
    "         for src, dest in itertools.permutations(sizes, 2)),\n",
    "))\n",
    "\n",
    "def search(target):\n",
    "    for n in itertools.count(1):\n",
    "        for ops in itertools.product(operations, repeat=n):\n",
    "            jugs = Jugs.fromkeys(sizes, 0)\n",
    "            states = [op(jugs) or tuple(jugs.values()) for op in ops]\n",
    "            if any(target in state for state in states):\n",
    "                return states\n",
    "\n",
    "%time search(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now to relentlessly simplify the code.  The first observation is that an empty source is useless, as is a full destination.  So the `fill` and `empty` primitives are actually unneeded, and can be integrated into the `pour` method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "CPU times: user 87 µs, sys: 0 ns, total: 87 µs\nWall time: 88.7 µs\n"
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[(3, 2), (2, 0), (3, 4)]"
     },
     "metadata": {},
     "execution_count": 3
    }
   ],
   "source": [
    "def pour(jugs, src, dest):\n",
    "    if not jugs[src]:\n",
    "        jugs[src] = src\n",
    "    if jugs[dest] >= dest:\n",
    "        jugs[dest] = 0\n",
    "    total = jugs[src] + jugs[dest]\n",
    "    jugs[src] = max(total - dest, 0)\n",
    "    jugs[dest] = min(total, dest)\n",
    "\n",
    "operations = [partial(pour, src=src, dest=dest) \n",
    "               for src, dest in itertools.permutations(sizes, 2)]\n",
    "\n",
    "%time search(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That reduced the search space considerably, but moreover has revealed another simplification: it's pointless to \"undo\" a pour.  Whether the source was emptied or the destination was filled, whatever reversing the previous pour direction would accomplish could have been done in the first place.\n",
    "\n",
    "If there were more than 2 jugs, then there could be complex workflows.  But with only 2, the first choice in pour directions determines the rest.  There are only 2 _potential_ solutions to the puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[(2, 3), (0, 2), (4, 3)]"
     },
     "metadata": {},
     "execution_count": 4
    }
   ],
   "source": [
    "def search(target, src, dest):\n",
    "    jugs = dict.fromkeys((src, dest), 0)\n",
    "    while True:\n",
    "        pour(jugs, src, dest)\n",
    "        yield tuple(jugs.values())\n",
    "        if target in jugs.values():\n",
    "            return\n",
    "\n",
    "list(search(4, 5, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[(0, 3), (1, 5), (0, 1), (0, 4)]"
     },
     "metadata": {},
     "execution_count": 5
    }
   ],
   "source": [
    "list(search(4, 3, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And both of them are valid solutions.  The solution to the puzzle is quite simply: keep pouring.  It doesn't even matter which to start with.\n",
    "\n",
    "But it can be further simplified.  Now it's clear that the `jug` data structure is only providing modular arithmetic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(2, -2)"
     },
     "metadata": {},
     "execution_count": 6
    }
   ],
   "source": [
    "def search(target, src, dest):\n",
    "    for n in itertools.count(1):\n",
    "        quot, rem = divmod(n * src - target, dest)\n",
    "        if not rem:\n",
    "            return n, -quot\n",
    "\n",
    "search(4, 5, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(3, -1)"
     },
     "metadata": {},
     "execution_count": 7
    }
   ],
   "source": [
    "search(4, 3, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "assert (5 * 2) - (3 * 2) == (3 * 3) - (5 * 1) == 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The puzzle is looking for integer solutions to\n",
    "$$\n",
    "\\ 3x + 5y = 4\n",
    "$$\n",
    "Which is known as a linear [Diophantine equation](https://en.wikipedia.org/wiki/Diophantine_equation), and must have a solution because $4$ is a multiple of $gcd(3, 5)$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "env": {},
   "interrupt_mode": "signal",
   "language": "python",
   "metadata": {},
   "name": "python3"
  },
  "nikola": {
   "category": "puzzles",
   "date": "2020-06-14",
   "description": "",
   "link": "",
   "slug": "water-pouring",
   "tags": "",
   "title": "Water pouring",
   "type": "text"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}